package com.ahs.algorithm;

import org.junit.jupiter.api.Test;

/**
 * @author riven zhang
 * @since 2021/9/1 14:55
 */
public class XSqrtRoot {

    /**
     * 常规算法
     */
    private int sqrt(int num) {
        int left = 1;
        int right = num >> 1;

        while (left < right) {
            int mid = (left + right) >> 1;
            int result = mid * mid;
            if (result == num) {
                return mid;
            }
            if (result > num) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        if (right * right > num) {
            return right - 1;
        }
        return right;
    }

    /**
     * 牛顿迭代法
     */
    private int newTown(int num) {
        return 0;
    }

    @Test
    void test() {
        int sqrt = sqrt(105);
        System.out.println("sqrt = " + sqrt);
    }
}
